package pers.qianyu.month_202011.date_20201116;

import pers.qianyu.util.*;

/**
 * 3. 无重复字符的最长子串
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 *
 * @author mizzle rain
 * @date 2020-11-16 14:04
 */
public class LengthOfLongestSubstring2 {
    /**
     * 优化左侧窗口收缩条件
     */
    public int lengthOfLongestSubstring(String s) {
        int left = 0, right = 0;
        int[] window = new int[128];
        int len = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            window[c]++;
            right++;
            while (window[c] > 1) {
                char c1 = s.charAt(left);
                window[c1]--;
                left++;
            }
            if (right - left > len) {
                len = right - left;
            }
        }
        return len;
    }

    private void printWindow(int[] window) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < window.length; i++) {
            int c = window[i];
            if (c > 0) {
                builder.append(String.format("{%s : %s}", (char) i, c));
            }
        }
        System.out.println(builder);
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        ArrayUtil.printIndex(s.length());
        int result = new LengthOfLongestSubstring2().lengthOfLongestSubstring(s);
        System.out.println("result = " + result);
    }
}
